#pragma once

#include "type.h"

#include "plane.h"
#include "vector2.h"

#include <stack>

/**
 *	This class finds a convex hull from the given array
 *	of Vector3 points, and a plane on which all the points lie.
 *	It uses the Graham Scan algorithm, which does the job in O(n log n) time.
 *  And This always used in 2D algorithm
 */
class GrahamScan
{
public:
	GrahamScan( std::vector<Common::Vector3>& rSrcPts )
		:m_srcPts( rSrcPts )
	{
		if( m_srcPts.size() < 3 )
			assert( !_T("points must be more than 3") );

		this->planeEquation(m_Plane);
		this->makeConvexHull();
	}

	typedef std::stack<Common::Vector3> Stack;

	void planeEquation( Common::Plane& result )
	{
		result.redefine( m_srcPts[0], m_srcPts[1], m_srcPts[2] );
	}

	// sorting function to find the point on the plane with the lowest Y value,
	// and given y values that are equal, the lowest X value.
	struct LowestYPlaneSort
	{
		bool operator()( const Common::Vector3& a, const Common::Vector3& b)
		{			
			if ( ::fabs( a.y - b.y ) < 0.0001f )
				return a.x < b.x;
			return a.y < b.y;
		}	
	};


	// sorting function by angle
	// (ignores z, assumes they are projected onto a plane)
	// note this algorithm assumes incoming points are above the fulcrum.
	// This assumption holds because the points are sorted by y position first.
	struct LowestAnglePlaneSort
	{
		LowestAnglePlaneSort( const Common::Vector3& fulcrum ):		
			m_fulcrum(fulcrum)
		{
		}

		bool operator()( const Common::Vector3& a, const Common::Vector3& b )
		{
			Common::Vector2 tanA( a.x - m_fulcrum.x, a.y - m_fulcrum.y) ;
			Common::Vector2 tanB( b.x - m_fulcrum.x, b.y - m_fulcrum.y) ;

			return ( (tanA.x*tanB.y) > (tanB.x*tanA.y) );
		}
	private:		
		Common::Vector3 m_fulcrum;
	};


	//annoying bit of code to retrieve the top + second entries on a stack.
	void findStackTop2( Stack& stack, Common::Vector3* pt )
	{		
		pt[1] = stack.top();		
		stack.pop();
		pt[0] = stack.top();
		stack.push(pt[1]);		
	}


	//Is pt on the left of the line made between pts[0] and pts[1] ?
	float isLeft( const Common::Vector3* pts, const Common::Vector3& pt )
	{
		return (pts[1].x - pts[0].x) * (pt.y - pts[0].y) - (pt.x - pts[0].x) * (pts[1].y - pts[0].y);
	}


	//Convert all our points into 2D plane space
	void projectPoints()
	{
		for (uint32 iPtsIdx = 0; iPtsIdx < m_srcPts.size(); iPtsIdx++)
		{
			Common::Vector2 prj = m_Plane.projectTo2DCoord( m_srcPts[iPtsIdx] );
			m_srcPts[iPtsIdx].x = prj.x;
			m_srcPts[iPtsIdx].y = prj.y;
		}
	}


	//Convert all our points back into 3D space.
	void unprojectPoints()
	{
		for (uint32 iPtsIdx = 0; iPtsIdx < m_srcPts.size(); iPtsIdx++)
		{
			Common::Vector2 param( m_srcPts[iPtsIdx].x, m_srcPts[iPtsIdx].y );
			m_srcPts[iPtsIdx] = m_Plane.unprojectTo3DCoord(param);
		}
	}


	/**
	 *	This method is the entry point for the algorithm.  It takes a vector of
	 *	3D points, 
	 */
	void makeConvexHull()
	{
		//Graham scan algorithm.

		//0. early out, any triangle would already be a convex hull.
		if (m_srcPts.size() <= 3)
			return;

		//From here in, we work in 2D space, with all points projected onto
		//the plane (GrahamScan only works on 2D hulls)
		this->projectPoints();

		//1. First find the fulcrum point, with the lowest Y projected onto the plane.
		std::sort( m_srcPts.begin(), m_srcPts.end(), LowestYPlaneSort() );
		
		//2. Sort the points by angle between them and the fulcrum point.
		std::sort( m_srcPts.begin()+1, m_srcPts.end(), LowestAnglePlaneSort( m_srcPts[0] ) );

		//3. Now go through the sorted list, discarding only left hand turns	
		Stack stack;
		stack.push(m_srcPts[0]);
		stack.push(m_srcPts[1]);

		Common::Vector3 pts[2];
		uint32 i = 2;
		float cp;
		while ( i < m_srcPts.size() )
		{		
			this->findStackTop2( stack, pts );

			cp = this->isLeft( pts, m_srcPts[i] );
			if (cp>0)
			{
				stack.push( m_srcPts[i] );
			}
			else
			{
				do
				{
					stack.pop();
					if (stack.size() > 2)
					{
						this->findStackTop2( stack, pts );						
						cp = this->isLeft(pts, m_srcPts[i]);
					}
				}
				while ( cp <= 0 && stack.size() > 2 );
				
				stack.push( m_srcPts[i] );
			}
			i++;
		}

		//Finally, check the last point is inside the hull.
		this->findStackTop2( stack, pts );
		cp = this->isLeft(pts,m_srcPts[0]);
		if (cp <= 0)
			stack.pop();
		
		//Now, put the results back in the list
		m_srcPts.clear();
		m_srcPts.resize( stack.size() );
		i = stack.size() - 1;
		while (!stack.empty())
		{
			m_srcPts[i] = stack.top();
			stack.pop();
			i--;
		}

		//And return to 3D space.
		this->unprojectPoints();
	}

private:
	Common::Plane m_Plane;
	std::vector<Common::Vector3>& m_srcPts;
};
